A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm

摘要

We show a Birthday Paradox for self-intersections of Markov chains withuniform stationary distribution. As an application, we analyze Pollard's Rhoalgorithm for finding the discrete logarithm in a cyclic group $G$ and findthat if the partition in the algorithm is given by a random oracle, then withhigh probability a collision occurs in $\Theta(\sqrt{|G|})$ steps. Moreover,for the parallelized distinguished points algorithm on $J$ processors we findthat $\Theta(\sqrt{|G|}/J)$ steps suffices. These are the first proofs of thecorrect order bounds which do not assume that every step of the algorithmproduces an i.i.d. sample from $G$.